home *** CD-ROM | disk | FTP | other *** search
/ PC Media 7 / PC MEDIA CD07.iso / share / prog / cm / cmthash.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-06  |  4.6 KB  |  102 lines
  1. // CmTHash.h
  2. // -----------------------------------------------------------------
  3. // Compendium - C++ Container Class Library
  4. // Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
  5. // -----------------------------------------------------------------
  6. // Hash table template definition.
  7. // -----------------------------------------------------------------
  8.  
  9. #ifndef _CMTHASH_H
  10. #define _CMTHASH_H
  11.  
  12. #include <cm/include/cmtcont.h>
  13.  
  14. template <class T> class CmTHashBucket;         // Bucket class stub.
  15. template <class T> class CmTHashNode;           // Node class stub.
  16. template <class T> class CmTHashTableIterator;  // Iterator class stub.
  17.  
  18. template <class T> class CmTHashTable : public CmTContainer<T> {
  19. public:
  20.   CmTHashTable(unsigned = 10);                  // Default table constructor.
  21.   CmTHashTable(const CmTHashTable<T>&);         // Table copy constructor.
  22.  ~CmTHashTable();                               // Table destructor.
  23.  
  24.   CmTHashTable<T>& operator=(const CmTHashTable<T>&);  // Assignment.
  25.  
  26.   void setHashFunction(unsigned (*pFunc)(const T&, unsigned));  // Set hasher.
  27.  
  28.   int      total      () const;                 // Return number of items.
  29.   Bool     add        (const T&);               // Add item to table.
  30.   Bool     remove     (const T&);               // Remove equal item from table.
  31.   const T& lookup     (const T&) const;         // Return equal item from table.
  32.   Bool     contains   (const T&) const;         // See if equal item in table.
  33.   unsigned occurrences(const T&) const;         // How many occurrences of item.
  34.   void     removeAll  ();                       // Remove all items.
  35.   Bool     resize     (unsigned);               // Resize the table.
  36.   Bool     isEmpty    () const;                 // Is table empty.
  37.  
  38.   CmTIterator<T>* newIterator() const;          // Create and return iterator.
  39.  
  40. protected:
  41.   unsigned (*_hFunc)(const T&, unsigned);       // Hash function pointer.
  42.  
  43.   int               _total;                     // Number of items in table.
  44.   Bool              _funcSet;                   // Is hash function set.
  45.   CmTHashBucket<T> *_buckets;                   // Hash bucket list.
  46.   friend            CmTHashTableIterator<T>;    // Iterator can access.
  47. };
  48.  
  49. template <class T> class CmTHashBucket {        // Bucket definition.
  50. protected:
  51.   CmTHashBucket() : _size(0), _first(NULL), _last(NULL) {}  // Constructor.
  52.  ~CmTHashBucket() { removeAll(); }              // Bucket destructor.
  53.  
  54.   unsigned size() const { return _size; }       // Return bucket size.
  55.  
  56.   Bool append   (const T&);                     // Append item to bucket.
  57.   Bool contains (const T&) const;               // Is item in bucket?
  58.   Bool remove   (const T&);                     // Remove item from bucket.
  59.   T*   lookup   (const T&) const;               // Return equal item.
  60.   void removeAll();                             // Remove all items.
  61.  
  62.   unsigned        _size;                        // Bucket size.
  63.   CmTHashNode<T> *_first;                       // First node in bucket.
  64.   CmTHashNode<T> *_last;                        // Last node in bucket.
  65.   friend          CmTHashTable<T>;              // Table can access.
  66.   friend          CmTHashTableIterator<T>;      // Iterator can access.
  67. };
  68.  
  69. template <class T> class CmTHashNode {          // Node definition.
  70. protected:
  71.   CmTHashNode(const T& O) : _next(NULL), _data(O) {}  // Constructor.
  72.  
  73.   CmTHashNode<T> *_next;                        // Next node in bucket.
  74.   T               _data;                        // Item.
  75.   friend          CmTHashBucket<T>;             // Bucket can access.
  76.   friend          CmTHashTableIterator<T>;      // Iterator can access.
  77. };
  78.  
  79. template <class T> class CmTHashTableIterator : public CmTIterator<T> {
  80. public:
  81.   CmTHashTableIterator(const CmTHashTable<T>&); // Iterator constructor.
  82.  
  83.   Bool     done    () const;                    // Check if done iterating.
  84.   const T& next    ();                          // Return and advance.
  85.   const T& previous();                          // Return and backup.
  86.   const T& current () const;                    // Return current item.
  87.   void     first   ();                          // Move to first item.
  88.   void     last    ();                          // Move to last item.
  89.  
  90. protected:
  91.   const CmTHashTable<T>& _table;                // Table being iterated.
  92.   int                    _bucket;               // Current hash bucket.
  93.   CmTHashNode<T>        *_node;                 // Current bucket node.
  94.   friend                 CmTHashTable<T>;       // Table can access.
  95. };
  96.  
  97. #if defined(__TURBOC__) || defined(__xlC__)
  98. #include <cm/include/cmthash.cc>
  99. #endif
  100.  
  101. #endif
  102.